Problem

Time limit : 3sec / Memory limit : 256MB

题意：

给定$n$个数的数组$A$和数组$B$，求所有$A_i+B_j$的异或和$(1\leq i,j \leq n)$。

$n \leq 200000$。

door♂

Solution

首先按位考虑，求所有的$a_i+b_j$中每个数位的xor和。

我们可以想到，如果有两个数x,y，且$0<x,y \leq 2^k$，那么当$0 \leq x+y<2^k$时，$x+y$在$2^k$这一位上的贡献肯定为$0$。
如果$2^{k+1} \leq x+y<2^{k+1}+2^k$，那么$x+y$在$2^k$这一位上的贡献依然为$0$，此时就相当于$x+y$在$2^k$这一位上的贡献被后面的数的进位抹去了。
用在计算答案的第$k$位时，把序列$a,b$中的数的最后$k$位算出来，设为$a’,b’$。
把$b’$排个序，二分找找$a’i+b’j>2^{k-1}$和$2^k \leq a’i+b’j<2^k+2^{k-1}$的方案数，两者相减后判断一下奇偶性。

Code:

Click to show/hide the code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
typedef long long ll;
using namespace std;
ll a[200010], b[200010];
ll tmp[200010];
int n;
inline ll chk(ll k)
{
	register int l = 1, r = n + 1;
	while (l < r)
	{
		register int mid = (l + r) >> 1;
		if (tmp[mid] >= k)r = mid; else l = mid + 1;
	}
	return l;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n; 
	for (register int i = 1; i <= n; i++) cin >> a[i];
	for (register int i = 1; i <= n; i++) cin >> b[i];
	register ll ans = 0;
	for (register int k = 1; k <= 29; k++)
	{
		register ll base = (1 << k) - 1;
		for (register int i = 1; i <= n; i++)tmp[i] = b[i] & base;
		sort(tmp + 1, tmp + n + 1);
		register ll cnt = 0;
		for (register int i = 1; i <= n; i++)
			cnt += n - chk((1 << (k - 1)) - (a[i] & base)) + 1;
		for (register int i = 1; i <= n; i++)
			cnt -= chk((1 << k) + (1 << (k - 1)) - (a[i] & base)) - chk((1 << k) - (a[i] & base));
		if (cnt & 1) ans += (1 << (k - 1));
	}
	cout << ans << endl; return 0;
}